package leetcode_400;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

/**
 *@author 周杨
 *ReconstructItinerary_332 给定一个有向图 寻找欧拉路径
 *describe:AC 26% DFS
 *2018年7月5日 上午11:59:47
 */
public class ReconstructItinerary_332 {
	private Map<String, PriorityQueue<String>> targets = new HashMap<>();
	private List<String> route = new LinkedList();
	
	public List<String> findItinerary(String[][] tickets) {
	    for (String[] ticket : tickets)
	        targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
	    visit("JFK");
	    return route;
	}
	 
	
	 
	void visit(String airport) {
	    while(targets.containsKey(airport) && !targets.get(airport).isEmpty())
	        visit(targets.get(airport).poll());
	    route.add(0, airport);
	}

}
